package com.剑指offer一;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 剑指 Offer 35. 复杂链表的复制
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年12月15日 18:49
 */
public class CopyRandomList {
    /**
     * 哈希表+链表
     * next 是左指针，random是右指针
     * @param head
     * @return
     */
    Map<Node,Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        Node move = head;
        Node dummy = new Node(0);
        Node newHead = new Node(0);
        dummy.next = newHead;
        while (move!=null){
            newHead.val = move.val;
            newHead.next = new Node(0);
            newHead.random = move.random;
            map.put(move,newHead);
            move = move.next;
            if (move == null){
                newHead.next = null;
                continue;
            }
            newHead = newHead.next;

        }


        newHead = dummy.next;
        while (newHead!=null){
            newHead.random = map.get(newHead.random);
            newHead = newHead.next;
        }
        return dummy.next;
    }

    /**
     * 递归实现
     */
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();
    public Node copyRandomList1(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            // 下面二者等价
            // headNew.random = cachedNode.get(head.random);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }





    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
